#include<iostream>
using namespace std;
const int MAX=9999999;
// const int n=5;  //这是第一个例子
// double p[n+1]={0,   0.15,0.10,0.05,0.10,0.20};
// double q[n+1]={0.05,0.10,0.05,0.05,0.05,0.10};
const int n=7;    //这是第二个例子
float p[n+1]={0,    0.04 ,0.06, 0.08, 0.02, 0.10, 0.12, 0.14};
float q[n+1]={0.06 ,0.06, 0.06, 0.06, 0.05, 0.05, 0.05, 0.05};
// const int n=4;
// float p[n+1]={0,0.1,0.2,0.3,0.4};
// float q[n+1]={0,0.1,0.4,}
double dp[n+1][n+1],w[n+1][n+1];
int root[n+1][n+1];
void findbest()
{
    for(int i=1;i<=n+1;i++)
    {
        dp[i][i-1]=q[i-1];//根据伪关键字最后一次是否计算来选择为0或q[i-1]
        w[i][i-1]=q[i-1];
        root[i][i]=i;
    }
    for(int d=0;d<=n;d++)
    {
        for(int i=1;i+d<=n;i++)
        {
            int l=i+d;
            w[i][l]=w[i][l-1]+p[l]+q[l];
            dp[i][l]=dp[i+1][l]+dp[i][i-1];
            root[i][l]=i;
            for(int j=i+1;j<=l;j++)
            {
                if(dp[i][j-1]+dp[j+1][l]<dp[i][l])
                {
                    dp[i][l]=dp[i][j-1]+dp[j+1][l];
                    root[i][l]=j;
                }
            }
            dp[i][l]+=w[i][l];
        }
    }
}
// void print(int i,int j)
// {
    // if(i==1&&j==n) 
    // cout<<"root=k"<<root[1][n]<<endl;
//     if(root[i][j]!=i)
//     {
        // cout<<"k"<<root[i][root[i][j]-1]<<" is "<<"left son of k"<<root[i][j]<<endl;
        // print(i,root[i][j]-1);
//     }
//     else cout<<"d"<<i-1<<" is "<<"left son of k"<<root[i][j]<<endl;

//     if(root[i][j]!=j)
//     {
//         cout<<"k"<<root[root[i][j]+1][j]<<" is "<<"right son of k"<<root[i][j]<<endl;
//         print(root[i][j]+1,j);
//     }
//     else cout<<"d"<<j<<" is "<<"right son of k"<<root[i][j]<<endl;
// }
void print(int i,int j,int last)
{
    if(i==last) 
    {
        cout<<"d"<<i-1<<" is "<<"left child of k"<<last<<endl;
        return;
    }
    if(j==last) {
        cout<<"d"<<j<<" is "<<"right child of k"<<last<<endl;
        return;
    }
    if(last==0) 
    cout<<"root="<<root[1][n]<<endl;
    else {
        if(j<last)
        cout<<"k"<<root[i][j]<<" is "<<"left child of k"<<last<<endl;
        else cout<<"k"<<root[i][j]<<" is "<<"right child of k"<<last<<endl;
    }
    print(i,root[i][j]-1,root[i][j]);
    print(root[i][j]+1,j,root[i][j]);
}
int main()
{
    findbest();
    cout<<dp[1][n]<<endl;
    print(1,n,0);
    // for(int i=1;i<=n+1;i++){
    //     for(int j=0;j<=n;j++){
    //         cout.width(5);
    //         cout << dp[i][j] << "   ";
    //     }
    //     cout << endl;
    // }
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=1;j<=n;j++)
    //     cout<<root[i][j]<<" ";
    //     cout<<endl;
    // }
}